[파이썬알고리즘인터뷰]#7 선형 자료구조
🔥 algorithm | February 17, 2021
💡
선형 자료구조란?
데이터 요소가 순차적으로 배열되는 자료구조를 선형(Linear) 자료구조라고 한다. 선형 자료구조는 단일 레벨로 구성된다. 따라서 한 번에 탐색이 가능하다. 배열, 스택, 큐, 연결 리스트 등이 모두 선형 자료형에 속한다.
배열
배열은 값 또는 변수 엘리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별된다.
자료구조 종류
- 메모리 공간 기반의 연속(Contiguous) 방식
- 포인터 기반의 연결(Link) 방식
배열은 연속 방식이 기본이 되는 자료형
파이썬의list는 동적 배열 자료형
동적 배열 자료형
크기를 자동으로 리사이징하는 배열
-
대부분의 언어에서 동적 배열 자료형을 제공한다.
- 메모리가 부족하면 자동으로 메모리를 채워주게 되는데, 일반적으로
더블링(Doubling)이라 하며, 2배씩 늘려나간다.
- 메모리가 부족하면 자동으로 메모리를 채워주게 되는데, 일반적으로
-
파이썬의 더블링은 초반에 2배씩 늘려나가지만, 뒤로 갈 수록 재할당하는 식의 방식으로 간극을 좁힌다.
- 기술된 수치만큼 재할당 하는 것을
그로스 팩터(Growth Factor)라고 하며,성장 인자라고도 불린다.
- 기술된 수치만큼 재할당 하는 것을
문제 - 두 수의 합
덧셈하여 타켓을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.
풀이 1 - 브루트 포스
def twoSum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
print(twoSum([2, 7, 11, 15], 9))- 이 풀이의 시간 복잡도는O(n^2)
풀이 2 - in을 이용한 탐색
def twoSum(nums, target):
for i, n in enumerate(nums):
complement = target - n
if complement in nums[i + 1:]:
return nums.index(n), nums[i + 1:].index(complement) + (i + 1)
print(twoSum([2, 7, 11, 15], 9))- 모든 조합을 비교하지 않고, 타켓에서 첫 번째 값을 뺀 값
target - n이 존재하는지 확인 in의 시간 복잡도는 O(n)으로 이전과 동일한 O(n^2)지만, 같은 시간 복잡도라면in이 더 빠르다.
풀이 3 - 첫 번째 수를 뺀 결과 키 조회
def twoSum(nums, target):
nums_map = {}
# 키와 값을 바꿔서 딕셔너리에 저장
for i, num in enumerate(nums):
nums_map[num] = i
# 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
for i, num in enumerate(nums):
if target - num in nums_map and i != nums_map[target - num]:
return nums.index(num), nums_map[target - num]
print(twoSum([2, 7, 11, 15], 9))- 해시테이블을 이용해,
target - n한 값을dict.key로 찾는 방법 - 시간 복잡도는 O(1)이며, 전체는 O(n)이다.
풀이 4 - 조회 구조 개선
def twoSum(nums, target):
nums_map = {}
# 하나의 for 문으로 통합
for i, num in enumerate(nums):
if target - num in nums_map:
return [nums_map[target - num], i]
nums_map[num] = i
print(twoSum([2, 7, 11, 15], 9))- 하나의 for 문으로 통합했다.
- 딕셔너리에 미리 값을 저장할 필요 없이, 바로 정답을 찾게 되는 구조
- 하지만 2 번째 값을 찾기 위해선 매번 비교해야 되기 때문에 위와 동일한 속도이지만, 더 간결해졌다.
풀이 5 - 투 포인터 이용
def twoSum(nums, target):
left, right = 0, len(nums) - 1
while not left == right:
# 합이 타겟보다 작으면 왼쪽 포인터를 왼쪽으로
if nums[left] + nums[right] < target:
left += 1
# 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로
elif nums[left] + nums[right] > target:
right -= 1
else:
return left, right
print(twoSum([2, 7, 11, 15], 9))- 왼쪽 포인터와 오른쪽 포인터의 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로, 작다면 왼쪽 포인터를 오른쪽으로 옮기면서 값을 조정하는 방식이다.
- 시간 복잡도 또한 O(n)이다.
-
이 문제의 문제점은 정렬이 되어 있는 상태를 기대해야 하고, 값이 아닌 index를 찾아 내는 것이라면 재정렬했을 때 index가 바뀌는 문제점이 발생된다.
- 반대로 값을 찾아내는 문제라면 언제든지 이 유형의 풀이가 유용하다.
문제 - 빗물 트래핑
높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.
풀이 1 - 투 포인터를 최대로 이동
def trap(height):
if not height:
return 0
volume = 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
while left < right:
left_max, right_max = max(height[left], left_max), \
max(height[right], right_max)
# 더 높은 쪽을 향해 투 포인터로 이동
# 가장 높은 곳에 왼쪽/오른쪽 모두 도착하면 return
# 현재 높이와의 차이만큼 물 높이 `volume`을 더해 나간다.(낮은 쪽은 그만큼 항상 채워짐)
if left_max <= right_max:
volume += left_max - height[left]
left += 1
else:
volume += right_max - height[right]
right -= 1
return volume
print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))- 가장 높은 쪽을 향해 왼쪽/오른쪽이 모두 욺직인다.
- 높이가 높은 곳 - 낮은 곳 (
volume += left_max - height[left]volume += right_max - height[right])은 물이 항상 채워지므로 그 수의 차이만큼volume을 더해 나간다. - 시간 복잡도는 O(n)이다.
풀이 2 - 스택 쌓기
def trap(height):
stack = []
volume = 0
for i in range(len(height)):
# 변곡점을 만나는 경우(현재 높이가 이전 높이보다 높을 경우에만)
while stack and height[i] > height[stack[-1]]:
# 스택에서 꺼낸다
top = stack.pop()
if not len(stack):
break
# 이전과의 차이만큼 물 높이 처리
distance = i - stack[-1] - 1 # 현재 위치랑 전 위치 간, 즉 변곡점 간의 거리 차이
waters = min(height[i], height[stack[-1]]) - height[top] # 쌓인 물의 양
volume += distance * waters
stack.append(i)
return volume
print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))문제 - 세 수의 합
배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.
풀이 1 - 브루트 포스로 계산
def threeSum(nums):
result = []
nums.sort()
# 브루투 포스 n^3 반복
for i in range(len(nums) - 2):
# 중복된 값 건너뛰기
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, len(nums) - 1):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
for k in range(j + 1, len(nums)):
if k > j + 1 and nums[k] == nums[k -1]:
continue
if nums[i] + nums[j] + nums[k] == 0:
result.append((nums[i], nums[j], nums[k]))
return result
print(threeSum([-1, 0, 1, 2, -1, -4]))-
앞뒤로 같은 값이 있을 경우, 이를 쉽게 처리하기 위해
sort()- 파이썬의 팀소트 시간 복잡도는
O(n log n)
- 파이썬의 팀소트 시간 복잡도는
-
중복된 값이 있을 수 있으므로
continue로 분기 처리j > i+1처럼+1를 해준 이유는, 앞에 if 조건문에서 앞뒤로 이미 체크했기 때문에, 한칸 더 간 인덱스부터 처리하기 위함- 예시) [1, 2, 3 ,4] 앞에서 1, 2 체크를 한 상태, [1, 2, 3, 4] 중 1, 2를 체크할 필요없이 2, 3를 체크하기 위해서
- 시간 복잡도는 O(n^3)이므로, 더 효율적인 알고리즘이 필요하다.
풀이 2 - 투 포인터로 합 계산
def threeSum(nums):
result = []
nums.sort()
for i in range(len(nums) - 2):
# 중복된 값 건너뛰기
if i > 0 and nums[i] == nums[i - 1]:
continue
# 간격을 좁혀가며 합 sum 계산 (재반복 할 때 마다 left 값이 +1 된 상태로 초기화)
left, right = i + 1, len(nums) - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum < 0:
left += 1
elif sum > 0:
right -= 1
else:
# sum = 0인 경우이므로 정답 및 스킵 처리
result.append((nums[i], nums[left], nums[right]))
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return result
print(threeSum([-1, 0, 1, 2, -1, -4]))- 투 포인터를 이용한 알고리즘,
0값을 찾아내 append 시키며,left, right증가/감소를 반복하며 답을 찾아낸다. - O(n^2) 로 수정해 풀이가 가능하다.
💡
투 포인터란?
일반적으로 시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략을 뜻하다. 범위를 좁혀 나가기 위해서는, 일반적으로 배열이 정렬되어 있을 때 유용하다.
위로 올라가기💨
